package features.advance.leetcode.string.medium;

import features.advance.leetcode.Solution;

import java.util.*;

/**
 * @author LIN
 * @date 2021-04-27
 */
public class Solution17 extends Solution {

    public List<String> letterCombinations(String digits) {
        List<String> combinations = new ArrayList<String>();
        if (digits.length() == 0) {
            return combinations;
        }
        Map<Character, String> phoneMap = new HashMap<Character, String>() {{
            put('2', "abc");
            put('3', "def");
            put('4', "ghi");
            put('5', "jkl");
            put('6', "mno");
            put('7', "pqrs");
            put('8', "tuv");
            put('9', "wxyz");
        }};
        backtrack(combinations, phoneMap, digits, 0, new StringBuffer());
        return combinations;
    }

    public void backtrack(List<String> combinations, Map<Character, String> phoneMap, String digits, int index, StringBuffer combination) {
        if (index == digits.length()) {
            combinations.add(combination.toString());
        } else {
            char digit = digits.charAt(index);
            String letters = phoneMap.get(digit);
            int lettersCount = letters.length();
            for (int i = 0; i < lettersCount; i++) {
                combination.append(letters.charAt(i));
                backtrack(combinations, phoneMap, digits, index + 1, combination);
                combination.deleteCharAt(index);
            }
        }
    }
    public List<String> letterCombinations1(String digits) throws Exception {
        if(digits == null || "".equals(digits)){
            return Collections.emptyList();
        }
        if(digits.length() > 4){
            throw new Exception("digits长度不能超过4！");
        }
        Map<Character,String> map = new HashMap<>(16);

        map.put('2',"abc");
        map.put('3',"def");
        map.put('4',"ghi");
        map.put('5',"jkl");
        map.put('6',"mno");
        map.put('7',"pqrs");
        map.put('8',"tuv");
        map.put('9',"wxyz");
        List<StringBuffer> list = new ArrayList<>();
        StringBuffer sb = new StringBuffer();
        List<String> ret = new ArrayList<>();
        for(int i=0;i<digits.length();i++){
            char obj = digits.charAt(i);
            String l = map.get(obj);
            if(l == null){
                return null;
            }
            List<String> tmp = new ArrayList<>();
            for(int j=0;j<l.length();j++){
                if(i==0){
                    ret.add(l.charAt(j)+"");
                }else{
                    for (int k = 0; k < ret.size(); k++) {
                        String s = ret.get(k);
                        s+=l.charAt(j);
                        tmp.add(s);
                        System.out.println(tmp);
                    }
                }
            }
            if(!tmp.isEmpty()){
                ret = tmp;
            }
        }
        Collections.sort(ret);
        return ret;
    }
    public static void main(String[] args) throws Exception {
        Solution17 solution17 = new Solution17() {
            /**
             *  最优解
             * @param digits
             * @return
             */
            @Override
            public List<String> letterCombinations(String digits) {
                List<String> ans = new ArrayList<>();
                if (digits.length() == 0) return ans;
                letterCombinations(digits.toCharArray(), 0, new char[digits.length()], ans);
                return ans;
            }

            public void letterCombinations(char[] digits, int di, char[] str, List<String> ans) {
                int l1, l2;
                if (digits[di] == '7') {
                    l1 = 112;
                    l2 = 116;
                } else if (digits[di] == '8') {
                    l1 = 116;
                    l2 = 119;
                } else if (digits[di] == '9') {
                    l1 = 119;
                    l2 = 123;
                } else {
                    l1 = 97 + (digits[di] - '2') * 3;
                    l2 = l1 + 3;
                }

                for (int i = l1; i < l2; i++) {
                    str[di] = (char) i;
                    System.out.println(di+":"+(char)i+":"+Arrays.toString(str));
                    if (di + 1 < digits.length) {
                        letterCombinations(digits, di + 1, str, ans);
                    } else {
                        ans.add(String.valueOf(str));
                        System.out.println(ans);
                    }
                }
            }
        };
        String str = "29";
        List<String> strings = solution17.letterCombinations(str);
        System.out.println(strings);

    }
}
